import java.util.LinkedList;

/**
 * 讲解：https://www.bilibili.com/video/BV1rv4y1H7o6?spm_id_from=333.788.videopod.episodes&vd_source=36dbb0f6eb577254888df3bf9b4ce456&p=182
 * https://leetcode.cn/problems/trapping-rain-water/description/
 *
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 */
public class LeetCode42 {

    public static void main(String[] args) {
        LeetCode42 leetCode42 = new LeetCode42();
        System.out.println(leetCode42.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));//6
    }

    /**
     * 使用单调栈
     * @param height
     * @return
     */
    public int trap(int[] height) {
        LinkedList<Data> stack = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            Data right = new Data(height[i], i);
            while(!stack.isEmpty() && stack.peek().height< right.height){
                Data pop = stack.pop();
                Data left = stack.peek();
                if(left !=null){
                    int with = right.index-left.index-1;
                    int h = Math.min(right.height, left.height)- pop.height;
                    sum+=with*h;
                }
            }
            stack.push(right);
        }
        return sum;
    }


    static class Data {
        int height;
        int index;

        public Data(int height, int index) {
            this.height = height;
            this.index = index;
        }
    }
}
